from heapq import *

from sortedcontainers import SortedSet


class SmallestInfiniteSet:

    def __init__(self):
        self.start = 0
        self.q = []

    def popSmallest(self) -> int:
        if len(self.q) == 0:
            self.start += 1
            return self.start
        else:
            self.q.pop()

    def addBack(self, num: int) -> None:
        if num <= self.start and num not in self.q:
            heappush(self.q, num)


class SmallestInfiniteSet:

    def __init__(self):
        self.start = 0
        self.q = SortedSet()

    def popSmallest(self) -> int:
        if len(self.q) == 0:
            self.start += 1
            return self.start
        else:
            return self.q.pop(0)

    def addBack(self, num: int) -> None:
        if num <= self.start:
            self.q.add(num)